Networks are a principal means of exchanging or transferring information, such as data, voice, text or video information, among communication devices, such as computer terminals, multimedia workstations, and videophones, connected to the networks. A network typically comprises switching nodes connected to each other, and to communication devices, by various links. Each link is characterized by a bandwidth or link capacity. Information input from the communication devices to the network may be of any form but is often formatted into fixed-length packets or cells.
When information is to be exchanged between two communication devices, a path, often referred to as a “virtual circuit” (VC), is established. The virtual circuit is comprised of a set of nodes and links connecting the two communication devices. One of the communication devices specifies the destination for the information, and the network delivers the information over the virtual circuit as though a dedicated circuit connected the two communication devices. Cells in transit between communication devices may temporarily be stored in buffers at nodes along the path of the virtual circuit pending sufficient available bandwidth on subsequent links along the path.
An important consideration in network operation is admission control and routing of virtual circuits. Admission control is the process of deciding whether or not to admit requests for establishing new virtual circuits in the network. Routing is the process of selecting a path through the network for the requested virtual circuit. In particular, the task is to determine which VC requests the network can admit and route. The admission and routing determination may take into account various factors, such as the network topology, current available network resources, and any quality-of-service commitments, such as guaranteed bandwidth or maximum cell loss probability, made to users of the network. The availability of network resources requires sufficient buffer space in the nodes and capacity in the links.
The admission control and routing problems are typically addressed together. For example, when a network receives a request to establish a virtual circuit between communication devices, the network may initially select, based on a first criterion, a set of potential paths on which the requested virtual circuit may be routed. One such first criterion is to select, as the set of potential paths, all possible paths between the communication devices passing through less than a specified number of nodes. The network will then route the virtual circuit request on a path in the set of potential paths according to a second criterion, for example, the virtual circuit will be routed on the path whose most heavily utilized link operates at the smallest percentage of its capacity. If no paths are in the set of potential paths or if no paths meet the second criterion, then the requested virtual circuit is not admitted.
The admission control/routing problem is complicated when a variable bit-rate (VBR) source or communications device seeks access to the network and requests a virtual circuit. The complication arises because the statistics which describe the variations in the information input from the VBR source to the network are often imprecise and thus it is difficult to predict the requirements for network resources, such as requirements for buffer space in network nodes and requirements for bandwidth or capacity in network links. For example, the bandwidth requirements of VBR sources typically vary with time, and the bandwidth variations typically are difficult to characterize. Thus, the admission/routing determination is made with information that may not accurately reflect the demands that the VBR source may place on the network thereby causing degraded network performance. More particularly, if the network resource requirements for a VBR source requesting a virtual circuit through the network are overestimated based on inaccurate characterizations of the VBR source, then the network will not run at full capacity in that a portion of the resources provided or allocated to the VBR source based on the estimate will frequently not be used. Alternatively, if network resources are underestimated, the VBR source will input more information to the network than the network had provided for, and thus the network may become congested and cells traversing the network may be lost. See, for example, Roch Guerin et al., “Equivalent Capacity and its Application to Bandwidth Allocation in High-Speed Networks,” IEEE J. Sel. Areas in Comm., Vol. 9, No. 7, pp. 968–981 (September 1991).
A method has been proposed for determining the network resources required by requests for virtual circuits and for using the resource requirements in the process of admitting and routing the virtual circuit requests. See, A. Elwalid, D, Mitra and R. Wentworth, “A new approach for allocating buffers and bandwidth to heterogeneous, regulated traffic in an ATM node,” IEEE J. Select. Areas. Commun., vol. 13, pp. 1115–1127 (1995) and U.S. Pat. No. 5,838,663, assigned to the assignee of the present invention, each incorporated by reference herein. The Elwalid method takes advantage of the statistical multiplexing effect of large buffers. The Elwalid method uses a two-phase approach for solving the two-resource (buffer space in the nodes and capacity in the links) allocation problem.
Generally, in the first phase, lossless multiplexing is considered, and a buffer-capacity allocation policy is used to make the two resources exchangeable, thus making the two-resource problem a single-resource problem. In the second phase, the effect of statistical multiplexing is analyzed for the single-resource system by using established techniques. The Elwalid method is based on a model of a multiplexer having a dedicated buffer and bandwidth for a plurality of inputs and a single output. More commonly, however, the buffer is shared by all the output ports. Thus, a need exists for a method and apparatus that determines the network resources required by requests for virtual circuits and for using the resource requirements in the process of admitting and routing the virtual circuit requests in a network environment where the buffer is shared by all the output ports.